//
// Created by liuwenwen on 12/17/2019.
//


#include <iostream>
#include <iomanip>
#include <stack>
#include <cstring>
#include <fstream>
#include <cstdlib>
#include <cstdio>
#include <string>

using namespace std;


//哈夫曼树的存储表示
typedef struct
{
    int weight;    // 权值
    int parent;    // 父节点
    int lChild;    // 左孩子下标
    int rChild;    // 右孩子下标
} HTNode, *HuffmanTree;


// 选择权值最小的两颗树
void SelectMin(HuffmanTree hT, int n, int &s1, int &s2)
{
    s1 = s2 = 0;

    int i;
    for (i = 1; i < n; ++i)
    {
        if (0 == hT[i].parent)
        {
            if (0 == s1)
            {
                s1 = i;
            } else
            {
                s2 = i;
                break;
            }
        }
    }
    if (hT[s1].weight > hT[s2].weight)
    {
        int t = s1;
        s1 = s2;
        s2 = t;
    }

    for (i += 1; i < n; ++i)
    {
        if (0 == hT[i].parent)
        {
            if (hT[i].weight < hT[s1].weight)
            {
                s2 = s1;
                s1 = i;
            } else if (hT[i].weight < hT[s2].weight)
            {
                s2 = i;
            }
        }
    }
}

// 构造有n个权值（叶子节点）的哈夫曼树
void CreateHuffmanTree(HuffmanTree &hT)
{
    int n, m;       // n代表叶子节点个数，m代表总节点个数
    n = 27;       // 输入叶子节点个数
    m = 2 * n - 1;        // 2n-1=n+n-1，n-1是因为n0=n2+1

    hT = new HTNode[m + 1];    // 0号节点不使用，用于保存节点数量
    for (int i = 1; i <= m; ++i)
    {
        hT[i].parent = hT[i].lChild = hT[i].rChild = 0;     // 各个数据初始化为0
    }
    int alphabet[27]={64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1,186};
    for (int i = 1; i <= 27; ++i)
    {
        hT[i].weight=alphabet[i-1];    // 输入权值
    }
    hT[0].weight = m;    // 用0号节点保存节点数量

    /****** 初始化完毕, 创建哈夫曼树 ******/
    for (int i = n + 1; i <= m; ++i)        // 从非叶子节点处开始遍历
    {
        int s1, s2;     // 定义两个节点的下标
        SelectMin(hT, i, s1, s2);       // 选择权值最小的两棵树

        hT[s1].parent = hT[s2].parent = i;      //
        hT[i].lChild = s1;    // 作为新节点的孩子
        hT[i].rChild = s2;    // 作为新节点的孩子
        hT[i].weight = hT[s1].weight + hT[s2].weight;    // 新节点为左右孩子节点权值之和
    }
}


// 计算WPL（供仅传参树的跟节点的函数调用）
int HuffmanTreeWPL(HuffmanTree hT, int i, int depth)
{
    if (hT[i].lChild == 0 && hT[i].rChild == 0)
    {
        return hT[i].weight * depth;
    }
    else
    {
        return HuffmanTreeWPL(hT, hT[i].lChild, depth + 1) + HuffmanTreeWPL(hT, hT[i].rChild, depth + 1);
    }
}

// 计算WPL（带权路径长度）
int HuffmanTreeWPL(HuffmanTree hT)
{
    return HuffmanTreeWPL(hT, hT[0].weight, 0);
}

stack<int> VisitNode(HuffmanTree hT, int i,stack<int> &code)
{
//    cout << "正在访问" << i << endl;
//    cout << "当前栈" << endl;
//    stack<int> temp;
//    while(!code.empty())
//    {
//        std::cout << code.top();
//        temp.push(code.top());
//        code.pop();
//    }
//    while(!temp.empty())
//    {
//        code.push(temp.top());
//        temp.pop();
//    }
//    cout << "当前栈输出完毕" << endl;
//    cout << code.size() << endl;
    if(hT[i].parent==0)
    {
        return code;
    } else if(hT[hT[i].parent].lChild==i)
    {
        code.push(0);
        VisitNode(hT, hT[i].parent, code);
        return code;
    } else if(hT[hT[i].parent].rChild==i)
    {
        code.push(1);
        VisitNode(hT, hT[i].parent, code);
        return code;
    } else
    {
        std::cout << "Error, can not find child" << std::endl;
        return code;
    }
}

// 输出哈夫曼树各节点的状态
void PrintHuffmanTree(HuffmanTree hT)
{
    cout << "index weight parent lChild rChild CharacterEncoding" << endl;
    cout << left;    // 左对齐输出
    for (int i = 1, m = hT[0].weight; i <= m; ++i)
    {
        cout << setw(5) << i << " ";
        cout << setw(6) << hT[i].weight << " ";
        cout << setw(6) << hT[i].parent << " ";
        cout << setw(6) << hT[i].lChild << " ";
        cout << setw(6) << hT[i].rChild << " ";
        if(i<=(m+1)/2)
        {
            stack<int> code;
            VisitNode(hT, i, code);
//            cout << "栈大小" << code.size() << endl;
            while(!code.empty())
            {
                std::cout << code.top();
                code.pop();
            }
        }
        std::cout << std::endl;
    }
}


// 输出哈夫曼树某个叶子节点的编码
void Print(HuffmanTree hT, int n)
{
    stack<int> code;
    VisitNode(hT, n, code);
//            cout << "栈大小" << code.size() << endl;
//    system("touch ./../CodeFile.txt");
    while(!code.empty())
    {
        char buffer[1000];
        sprintf(buffer, R"(echo "%d\c" >> ./../CodeFile.txt)", code.top());
//        sprintf(buffer, ">>./../CodeFile.txt set /p=\"%d\" </dev/null", code.top());
//        std::cout << buffer << std::endl;
        std::cout << code.top();
        system(buffer);
        code.pop();
    }
}

char* Decode(HuffmanTree hT, char *p)
{
    if(p== nullptr || p[0] == '\0')
    {
        return nullptr;
    }
    int n=(hT[0].weight+1)/2;
    int i=0;
    int currentNode=hT[0].weight;
    for(i=0;p[i]!='\0';i++)
    {
        if(currentNode<=n)
        {
            break;
        }
        if(p[i]=='0')
        {
            currentNode=hT[currentNode].lChild;
        } else if(p[i]=='1')
        {
            currentNode=hT[currentNode].rChild;
        }
    }
//    std::cout << currentNode << std::endl;
    char buffer[1000];
    if(currentNode==27)
    {
        printf(" ");
        sprintf(buffer, R"(echo " \c" >> ./../TextFile.txt)");
        system(buffer);
    } else
    {
        printf("%c", char(int('a')-1+currentNode));
        sprintf(buffer, R"(echo "%c\c" >> ./../TextFile.txt)", char(int('a')-1+currentNode));
        system(buffer);
    }
    Decode(hT, p+i);
    return nullptr;
}

// 销毁哈夫曼树
void DestroyHuffmanTree(HuffmanTree &hT)
{
    delete[] hT;        // 释放数组hT的内存空间
    hT = nullptr;       // 将hT的指针置为空
}

int main(int argc, char *argv[])
{
    system("rm ./../CodeFile.txt");
    system("rm ./../TextFile.txt");
//    int alphabet[27]={64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1,186};
    HuffmanTree hT;
    CreateHuffmanTree(hT);
    PrintHuffmanTree(hT);
    cout << "WPL = " << HuffmanTreeWPL(hT) << endl;
    while(true)
    {
        char cache[100];
        printf("---------菜单--------\n");
        printf("1.从终端读入文本进行编码\n");
        printf("2.从终端读入编码进行解码\n");
        printf("3.从文件读入文本进行编码\n");
        printf("4.从文件读入编码进行解码\n");
        printf("5.按q退出...\n");
        printf("请输入选项：\n");
        scanf("%[^\n]%*c", cache);
        if(strcmp(cache, "q")==0)
        {
            break;
        } else if(strcmp(cache, "1")==0)
        {
            char buffer[1000];
            printf("请输入文本：\n");
            scanf("%[^\n]%*c", buffer);
            printf("文本编码是：\n");
            for(int i=0;buffer[i]!='\0';i++)
            {
                if(buffer[i]=='\40')
                {
                    Print(hT, 27);
                } else
                {
                    Print(hT, int(buffer[i]-'a')+1);
                }
            }
            std::cout << std::endl;
            system("echo >> ./../CodeFile.txt");
            printf("编码文本已存入CodeFile.txt中\n");
        } else if(strcmp(cache, "2")==0)
        {
            char buffer[1000];
            printf("请输入编码：\n");
            scanf("%[^\n]%*c", buffer);
            printf("文本解码是：\n");
            Decode(hT, buffer);
            std::cout << std::endl;
            system("echo >> ./../TextFile.txt");
            printf("解码文本已存入TextFile.txt中\n");
        } else if(strcmp(cache, "3")==0)
        {
            char buffer[1000];      //定义一个数组，用来存放字符
            printf("正在从ToBeTran中读取文本：\n");
            ifstream exampleFile("./../ToBeTran.txt");       //声明一个对象与要读的文件联系
            if (! exampleFile.is_open())        // 判断文件是否打开失败
            {
                cout << "Error opening file"; exit (1);
            }
            while (!exampleFile.eof())
            {
                cout << "文件中的文本是：" << endl;
                exampleFile.getline(buffer,1000);
                cout << buffer << endl;
                printf("文本编码是：\n");
                for(int i=0;buffer[i]!='\0';i++)
                {
                    if(buffer[i]=='\40')
                    {
                        Print(hT, 27);
                    } else
                    {
                        Print(hT, int(buffer[i]-'a')+1);
                    }
                }
                system("echo >> ./../CodeFile.txt");
                std::cout << std::endl;
            }
        } else if(strcmp(cache, "4")==0)
        {
            char buffer[1000];      //定义一个数组，用来存放字符
            printf("正在从CodeFile中读取文本：\n");
            ifstream exampleFile("./../CodeFile.txt");       //声明一个对象与要读的文件联系
            if (! exampleFile.is_open())        // 判断文件是否打开失败
            {
                cout << "Error opening file"; exit (1);
            }
            while (!exampleFile.eof())
            {
                exampleFile.getline(buffer,1000);
                if(strcmp(buffer, "\0")==0)
                {
                    continue;
                }
                cout << "文件中的编码是：" << endl;
                cout << buffer << endl;
//                cout << strlen(buffer) << endl;
//                cout << int(buffer[0]) << endl;
                printf("文本解码是：\n");
                Decode(hT, buffer);
                system("echo >> ./../TextFile.txt");
                std::cout << std::endl;
            }
        } else
        {
            printf("请重新输入序号！！！\n");
            continue;
        }
    }
//    char buffer[1000];
//    printf("请输入文本：\n");
//    scanf("%[^\n]%*c", buffer);
//    printf("文本编码是：\n");
//    for(int i=0;buffer[i]!='\0';i++)
//    {
//        if(buffer[i]=='\40')
//        {
//            Print(hT, 27);
//        } else
//        {
//            Print(hT, int(buffer[i]-'a')+1);
//        }
//    }
//    std::cout << std::endl;
//    printf("请输入编码：\n");
//    scanf("%[^\n]%*c", buffer);
//    printf("文本解码是：\n");
//    Decode(hT, buffer);
//    std::cout << std::endl;
    DestroyHuffmanTree(hT);
    return 0;
}
